Всего: 223 1–20 | 21–40 | 41–60 | 61–80 …
Добавить в вариант
1.1 Докажите, что в любой момент может произойти миграция.
Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
Представим архипелаг в виде графа. Тогда наша система — дерево с неотрицательным числом в каждой вершине (равным числу колоний на соответствующем острове); сумма всех чисел равна n. Если мигрировать нельзя, каждое число меньше соответствующей степени хотя бы на единичку. Суммируя неравенства по всем вершинам, получаем:
Противоречие.
1.2 Докажите, что как бы колонии тупиков не располагались изначально, миграциями можно расселить колонии по одной на остров.
Индукция по числу вершин.
База тривиальна.
Переход. Докажем, что в любой вершине можно получить не 0. Подвесим дерево за эту вершину. Рассмотрим такой полуинвариант: сумма по всем вершинам величин 
где xi — число в вершине, di — её глубина в подвешенном дереве. Легко видеть, что каждая миграция не из корня дерева отдаёт единичку наверх и менее n на уровень вниз, то есть сумма строго увеличивается. Но всех возможных сумм конечное число, так что рано или поздно будет возможна миграция только из корня, а это значит, что там
Теперь, собственно, переход. Рассмотрим лист v, при необходимости делаем там не 0 (мы только что доказали, что это возможно). Теперь отдаём из v всё, кроме 1, его соседу u. Рассмотрим последовательность миграций, делающую единички в дереве без v (она берётся из индукционного предположения). Применим её, только перед каждой миграцией из u будем отдавать туда 1 из v.
1.2 Докажите, что как бы колонии тупиков не располагались изначально, миграциями можно расселить колонии по одной на остров.
Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
Индукция по числу вершин.
База тривиальна.
Переход. Докажем, что в любой вершине можно получить не 0. Подвесим дерево за эту вершину. Рассмотрим такой полуинвариант: сумма по всем вершинам величин где xi — число в вершине, di — её глубина в подвешенном дереве. Легко видеть, что каждая миграция не из корня дерева отдаёт единичку наверх и менее n на уровень вниз, то есть сумма строго увеличивается. Но всех возможных сумм конечное число, так что рано или поздно будет возможна миграция только из корня, а это значит, что там
Теперь, собственно, переход. Рассмотрим лист v, при необходимости делаем там не 0 (мы только что доказали, что это возможно). Теперь отдаём из v всё, кроме 1, его соседу u. Рассмотрим последовательность миграций, делающую единички в дереве без v (она берётся из индукционного предположения). Применим её, только перед каждой миграцией из u будем отдавать туда 1 из v.
1.1 Докажите, что в любой момент может произойти миграция.
Представим архипелаг в виде графа. Тогда наша система — дерево с неотрицательным числом в каждой вершине (равным числу колоний на соответствующем острове); сумма всех чисел равна n. Если мигрировать нельзя, каждое число меньше соответствующей степени хотя бы на единичку. Суммируя неравенства по всем вершинам, получаем:
Противоречие.
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна 
а сумма соответствующих углов между хордой и касательной 
2.2 Пусть C и D совпали с точками касания окружностей и угла. Чему может быть равен угол ADR?
Треугольник RAB равносторонний: 
и 
по симметрии. Отсюда симметричные отрезки RA, RB образуют со сторонами углы, равные 
и этому же равен 
(т. к. 
Ответ: 15°.
2.2 Пусть C и D совпали с точками касания окружностей и угла. Чему может быть равен угол ADR?
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Треугольник RAB равносторонний: и по симметрии. Отсюда симметричные отрезки RA, RB образуют со сторонами углы, равные и этому же равен (т. к.
Ответ: 15°.
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
3.1 Пусть p = 7. Приведите пример таких 
при которых искомой пары не будет.
Сюжет 3
Миша взял простое число p > 2 и вот-вот выпишет на доску в ряд числа
Затем он хочет отыскать среди них пару чисел, дающих одинаковые остатки от деления на p.
Все возможные пары по модулю 7 — это (1, 3), (3, 3), (1, 5) и (5, 5).
Ответ: (1, 3), (3, 3), (1, 5), (5, 5).
3.2 Пусть a = 4, b = 3. Докажите, что будет искомая пара, содержащая одно из крайних чисел.
Если 
то всё ясно. Если 
то по Малой Теореме Ферма
Иначе же 
Например, потому что из МТФ 
значит,
Тогда
3.2 Пусть a = 4, b = 3. Докажите, что будет искомая пара, содержащая одно из крайних чисел.
Сюжет 3
Миша взял простое число p > 2 и вот-вот выпишет на доску в ряд числа
Затем он хочет отыскать среди них пару чисел, дающих одинаковые остатки от деления на p.
Если то всё ясно. Если то по Малой Теореме Ферма
Иначе же Например, потому что из МТФ значит,
Тогда
3.1 Пусть p = 7. Приведите пример таких при которых искомой пары не будет.
Все возможные пары по модулю 7 — это (1, 3), (3, 3), (1, 5) и (5, 5).
Ответ: (1, 3), (3, 3), (1, 5), (5, 5).
1.3 Докажите, что число колоний на данном острове никогда не превысит количество соседних с ним островов более,
Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
Покажем, что любое доступное распределение чисел на дереве можно получить, организуя миграции так, чтобы каждая колония уходила не дальше, чем на соседний остров. Из этого сразу следует требуемое утверждение.
Доказываем индукцией по числу миграций. База: ноль миграций, очевидна.
Переход. Пусть вот-вот произойдёт миграция с острова v. По предположению индукции, все находящиеся на нем колонии — с него и соседних островов. Раз можно мигрировать, то на острове
есть колонии хотя бы с 
соседних островов; отправим их обратно на свои острова. Если есть колония с оставшегося соседнего острова, тоже отправим её обратно, если есть своя колония, отправим её на любой из соседних островов.
1.1 Докажите, что в любой момент может произойти миграция.
Представим архипелаг в виде графа. Тогда наша система — дерево с неотрицательным числом в каждой вершине (равным числу колоний на соответствующем острове); сумма всех чисел равна n. Если мигрировать нельзя, каждое число меньше соответствующей степени хотя бы на единичку. Суммируя неравенства по всем вершинам, получаем:
Противоречие.
1.4 Произошло некоторое число миграций. После этого на каждый остров высадилось по орнитологу. Каждый орнитолог может перелететь на другой остров на личном вертолёте по тем же воздушным коридорам. Однако в целях безопасности в течение суток запрещено взлетать с соседних островов и пролетать дважды по одному и тому же коридору или над одним и тем же островом. Докажите, тем не менее, что некоторые орнитологи могут за сутки переместиться на другие острова, чтобы на каждом острове орнитологов и колоний тупиков оказалось поровну.
Сюжет 1
В архипелаге есть n скалистых островов, на них обитают n колоний ту́пиков (каждая колония целиком гнездится на одном острове). Некоторые пары островов соединены воздушными коридорами, причём от каждого острова до любого другого есть ровно один путь по этим коридорам. Острова, соединённые коридором, считаются соседними. Иногда происходят миграции: с некоторого острова на каждый соседний переселяется по колонии тупиков.
По соображению из прошлого решения можно считать, что каждая колония ушла не далее, чем на соседний остров. То, на какой остров будет отправляться каждая колония при миграции, будем выбирать, как в индукционном предположении предыдущего пункта. Нарисуем на ребре дерева стрелку, если колония переместилась между соответствующими островами, направление стрелки соответствует направлению перемещения колонии.
Заметим три факта:
1) из каждой вершины выходит не более одной стрелки;
2) на каждом ребре расположено не более одной стрелки. Действительно, пусть есть есть две стрелки между вершинами u и v, они в разных направлениях. Пусть стрелка из u в v появилась второй. Но когда она появлялась в u была колония из v, которая отправилась бы обратно, т. е. по нашему построению, не было бы ни одной из стрелок;
3) среди вершин, из которых есть стрелки, но в которые стрелок нет, нет двух соседних. Это так, потому что иначе бы в дереве было два нуля рядом, а так не бывает: последняя миграция из соответствующих двух вершин ломает второй ноль.
Всё, теперь из каждой вершины, в которую нет стрелочек, вертолёт летит по стрелочкам до упора, видно, что условия задачи выполняются.
1.1 Докажите, что в любой момент может произойти миграция.
Представим архипелаг в виде графа. Тогда наша система — дерево с неотрицательным числом в каждой вершине (равным числу колоний на соответствующем острове); сумма всех чисел равна n. Если мигрировать нельзя, каждое число меньше соответствующей степени хотя бы на единичку. Суммируя неравенства по всем вершинам, получаем:
Противоречие.
2.3 Докажите, что если угол R прямой, то точки C и D совпадают с точками касания окружностей и угла.
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Выполним инверсию i относительно центра окружности с центром в A и радиусом AB. Имеем 
и наши две окружности превращаются в прямые BC, BD, образующие прямой угол, а стороны исходного угла — в пару окружностей, вписанных в этот угол, перпендикулярных друг другу (как и соответствующие прямые до инверсии) и пересекающихся в точках A, i(R). Вычислим отношение их радиусов — это легко делается применением теоремы Пифагора к треугольнику AO1O2 со сторонами r1, r2, 
(O1, O2 — центры новых окружностей, 
—
будем считать 
Введём связанную с нашим прямым углом систему координат, тогда центры имеют координаты (1, 1) и 
а точки касания:
Середина 
—
и считая расстояние от неё до O1, O2 убеждаемся, что это точка пересечения наших окружностей, как и середина 
Значит, эти середины — точки A, i(R). Поскольку A не лежит на биссектрисе угла, то прямая, из которой наш угол высекает отрезок с серединой A — единственна, так что соответствующая пара точек X, Yi совпадает с
Есть решение и без инверсий.
Из условия легко следует, что радиусы окружностей перпендикулярны: отрезки AC и AD симметричны AB относительно соответствующих радиусов, а C, A, D лежат на одной прямой.
Кроме того, из этой симметричности ясно, что такие точки C и D единственны. Значит, если покажем, что точки касания подходят на их роль, мы победим. Пусть радиус маленькой окружности равен 1, большой — R. Тогда из теоремы Пифагора 
у этого уравнения ровно одно решение, где 
Пусть C′, D′ — точки касания первой и второй окружностей разных сторон угла. Введём систему координат параллельно сторонам угла, тогда 
Пусть A′ — середина этого отрезка, тогда не очень трудно проверить, что она лежит на обеих
То есть можно считать 
Осталось убедиться, что
Тогда
(последнее равенство можно проверить, возведя в квадрат). По симметрии точка B имеет координаты 
значит,
Ура!
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
2.4 Пусть 
Перпендикуляр из A на ближайшую сторону угла пересекает меньшую окружность в точке P, а перпендикуляр из A на вторую сторону пересекает BP в точке Q. Наконец, пусть O1 и O 2 — центры исходных окружностей, O — центр окружности, описанной около 
Докажите, что BO — биссектриса угла O1BO2.
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Исполним ту же самую инверсию, что и в предыдущем пункте, вновь получим прямой угол и вписанную в него пару окружностей, пересекающихся под углом 135°. Перпендикуляр AP перейдёт в диаметр, большей из окружностей, а сама точка i(P) его пересечение со стороной угла. Перпендикуляр на вторую сторону перейдет в диаметр меньшей из окружностей.
Теперь четырехугольник 
—
(половина прямого угла, в который вписаны окружности), а 
так как это угол между окружностями равный углу, между исходными прямыми. С другой стороны, по построению пересечение окружности 
с прямой AU это как раз i(Q). Значит, i(Q) лежит на биссектрисе угла, то есть (сделаем инверсию), окружность BQA образует равные углы с двумя исходными окружностями, а это именно то, что просят установить в задаче (радиус третьей окружности в точку пересечения - биссектриса первых двух радиусов).
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
3.3 Докажите, что у него получится, если a = 4, b = 7.
Сюжет 3
Миша взял простое число p > 2 и вот-вот выпишет на доску в ряд числа
Затем он хочет отыскать среди них пару чисел, дающих одинаковые остатки от деления на p.
Случаи 
разбираются руками.
1) Когда 
этот случай делается точно так же, как в 3.2;
2) Когда 
Тогда
значит, если все 
остатков различны, их сумма не равна 0. Но с другой стороны, суммируя две геометрические прогрессии, получаем
Это выражение равно 0 по МТФ.
3.1 Пусть p = 7. Приведите пример таких при которых искомой пары не будет.
Все возможные пары по модулю 7 — это (1, 3), (3, 3), (1, 5) и (5, 5).
Ответ: (1, 3), (3, 3), (1, 5), (5, 5).
3.4 Докажите, что у него получится, если 
— простое, a = 2 и b = 3.
Сюжет 3
Миша взял простое число p > 2 и вот-вот выпишет на доску в ряд числа
Затем он хочет отыскать среди них пару чисел, дающих одинаковые остатки от деления на p.
Лемма 1. Пусть 
простое 
таково, что для любого 
число xu остаток kx от деления на q имеют разную чётность. Тогда 
Доказательство леммы 1. Подставляя 
получаем, что k чётно, а значит kx всегда чётно, тогда остаток kx имеет ту же четность, что и неполное частное 
Теперь подставляем 
тогда 
и нечетно, то есть 
Теперь подставляем 
тогда 
и 
четно, то етсь 
Продолжая это, доходим до равенства
что невозможно при 
значит, 
Следствие 1. Пусть q простое, k нечётное, 
не кратно 2q. Тогда найдется l такое, что у обоих чисел l, kl остатки по модулю 2q строго между 0 и q.
Доказательство. Действительно, попробуем в качестве l все числа от 1 до 
Пусть все пары l, kl не подошли, то есть все kl имеют остатки по модулю 2q, большие q. Это значит, что чётность остатка kl по модулю q противоположна четности остатка kl по модулю 2q (q — нечётно), а она совпадает с четностью l (т. к. k нечётно) и мы попадаем в условия леммы.
Перейдём к решению задачи. Предположим, что все остатки различны. Посмотрим, на порядки 2 и 3 по модулю p. По МТФ они могут быть равны лишь 1, 2, q, 
(порядок a по модулю p — минимальное натуральное k такое, что 
(или числитель соответствующей несократимой дроби, если a — дробь) кратно p, это k мы будем обозначать 
Первые два случая проигнорируем, а случаи, когда хотя бы один из порядков равен q идентичны разобранным в пунктах 1 и 3. Пусть порядки 2q, в частности все остатки 
различны (иначе, если 2a и 2b дают одинаковые остатки, то 
а значит и 
кратно p, но 
и найдётся такое m, что 
Отметим также, что в этом случае 
так что если при некотором k имеем 
то и
так что нарушается условие различности остатков. Поэтому в нашей последовательности встречаются по разу все ненулевые остатки.
Подберём по следствию 1 такое 
что −ml при делении на 2q имеет остаток меньше q, назовём этот остаток r, 
делится на 2q.
Теперь изучим сумму
по модулю p. С одной стороны, выражение в скобках пробегает все ненулевые остатки, а число 
не 
и она равна нулю.
Посчитаем эту же сумму другим способом. Раскрыв все скобки по биному, перегруппировав слагаемые и переставив множители в показателях степеней, мы получим сумму геометрических прогрессий вида
Докажем, что ровно одна из этих прогрессий постоянна, а значит, ровно одно из указанных выражений ненулевое (тут надо отметить, что 
так что 
поэтому появляющиеся биномиальные коэффициенты не кратны p). Это даст требуемое противоречие.
Действительно, при 
получаем, учитывая 
что 
так как 
делится на 2q. С другой стороны, если 
при некотором 
то, деля, получаем 
то есть 
Получаем, что
значит, 
равен 1 или 2, что может быть лишь при 
этот случай проверяется непосредственно.
3.1 Пусть p = 7. Приведите пример таких при которых искомой пары не будет.
Все возможные пары по модулю 7 — это (1, 3), (3, 3), (1, 5) и (5, 5).
Ответ: (1, 3), (3, 3), (1, 5), (5, 5).
1.1 Найдите a (2, 2).
Сюжет 1
На n карточках написали по k чисел, сумма на каждой карточке равна m. Оказалось, что любой набор из k неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть a(n, k) — наименьшее m, при котором это возможно.
Пример: наборы 
и 
Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать (1; 0), и набор, в котором оба числа 
Если это одна и та же пара, то сумма уже 
Если разные, то посмотрим на набор 
чтобы набор 
мажорировал его, должно быть 
а чтобы набор с парой чисел, больших 
мажорировал — это должен быть набор, как минимум Легко видеть также, что указанный набор подходит.
Ответ: 
1.2 Докажите, что найдется n такое, что 
Рассмотрим все возможные способы записать число 
в виде суммы положительных рациональных дробей со знаменателем 10200 (не обязательно несократимых). Очевидно, что это количество конечно, его и обозначим
значит, получится один из наших наборов или аналогичный набор с меньшей суммой. Произвольно увеличив числители некоторых дробей так, чтобы сумма стала равной 
мы превратим набор в числа на одной из карточек, которая, таким образом, мажорирует исходный набор с единичной суммой.
1.2 Докажите, что найдется n такое, что
Сюжет 1
На n карточках написали по k чисел, сумма на каждой карточке равна m. Оказалось, что любой набор из k неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть a(n, k) — наименьшее m, при котором это возможно.
Рассмотрим все возможные способы записать число в виде суммы положительных рациональных дробей со знаменателем 10200 (не обязательно несократимых). Очевидно, что это количество конечно, его и обозначим
значит, получится один из наших наборов или аналогичный набор с меньшей суммой. Произвольно увеличив числители некоторых дробей так, чтобы сумма стала равной мы превратим набор в числа на одной из карточек, которая, таким образом, мажорирует исходный набор с единичной суммой.
1.1 Найдите a (2, 2).
Пример: наборы и
Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать (1; 0), и набор, в котором оба числа Если это одна и та же пара, то сумма уже Если разные, то посмотрим на набор чтобы набор мажорировал его, должно быть а чтобы набор с парой чисел, больших мажорировал — это должен быть набор, как минимум Легко видеть также, что указанный набор подходит.
Ответ:
2.1 Пусть С и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной 
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
2.2 Пусть C и D совпали с точками касания окружностей и угла. Чему может быть равен угол ADR?
Сюжет 2
Две окружности, вписанные в угол с вершиной R, пересекаются в точках A и B. Через A проведена прямая, пересекающая меньшую окружность в точке C, а большую — в точке D. Оказалось, что AB = AC = AD.
Треугольник RAB равносторонний — 
и по симметрии. Отсюда симметричные отрезки RA, RB образуют со сторонами углы, равные и этому же равен (так как
Ответ: 15°.
2.1 Пусть C и D совпали с точками касания окружностей и угла. Докажите, что угол R прямой.
Треугольник BCD прямоугольный (медиана — половина гипотенузы). Значит, сумма дуг AC и AD соответствующих окружностей равна а сумма соответствующих углов между хордой и касательной
3.1 Пусть a = 4, b = 9. Докажите, что искомая пара найдётся.
Сюжет 3.
В этом сюжете разрешается использовать (без обоснования) так называемую малую теорему Ферма, гласящую, что для всякого целого числа а и простого натурального числа p справедливо соотношение «a−a p делится на p без остатка».
Итак, 
—
значения, дающие одинаковые остатки от деления на p.
По МТФ 
но в то же время и
3.2 Пусть a = 4, b = 3. Докажите, что найдётся искомая пара, содержащая одно из крайних чисел.
Случаи разбираются руками. Дальше, аналогично предыдущим пунктам, если 
то всё ясно. 
получаем
Если бы остатки не повторялись, каждый бы встречался по разу, и тогда их сумма была бы равна 0. Но тут, как мы видим, их сумма равна
3.2 Пусть a = 4, b = 3. Докажите, что найдётся искомая пара, содержащая одно из крайних чисел.
Сюжет 3.
В этом сюжете разрешается использовать (без обоснования) так называемую малую теорему Ферма, гласящую, что для всякого целого числа а и простого натурального числа p справедливо соотношение «a−a p делится на p без остатка».
Итак, —
значения, дающие одинаковые остатки от деления на p.
Случаи разбираются руками. Дальше, аналогично предыдущим пунктам, если то всё ясно. получаем
Если бы остатки не повторялись, каждый бы встречался по разу, и тогда их сумма была бы равна 0. Но тут, как мы видим, их сумма равна
3.1 Пусть a = 4, b = 9. Докажите, что искомая пара найдётся.
По МТФ но в то же время и
1.3 Докажите, что 
Сюжет 1
На n карточках написали по k чисел, сумма на каждой карточке равна m. Оказалось, что любой набор из k неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть a(n, k) — наименьшее m, при котором это возможно.
Рассмотрим, например, следующую пару наборов:
Сумма в каждом равна 
это даже меньше, чем 1,71, а 
Проверим, что эта пара наборов мажорирует все нужные четвёрки. Ясно (*), что в упорядоченной тройке с суммой x среднее число — не больше, чем 
а малое — не больше, чем 
аналогичное верно для четвёрок. Действительно, если максимальное число в четвёрке больше 
то второе по величине — не больше, чем 
третье не больше 
а самое маленькое не 
то оно мажорируется первым набором.
Как прийти к этому решению?
Рассмотрим ситуацию, в которой в первой четверке максимальное число равно 1, а во второй 
Заметим, что для 
и вторая наша четверка сделать этого не сможет. Значит, второе слева число в первой четверке не меньше 
Теперь, рассмотрев для всех четверки вида
получим, что третье число в первой четверке не меньше, чем 
а рассмотрев для четверки вида
что четвертое число первой четверки — это хотя бы 
Значит, сумма в первой четверке хотя бы
Далее разберем случай, в котором четверки
накрываются второй суммой. Тогда четверка 
также накрывается второй суммой (если мы, конечно, не хотим сумму в первой четверке, большую 1,75). В такой ситуации второе число во второй четверке хотя бы третье — хотя бы 
четвертое — хотя бы 
Значит, сумма во второй четверке хотя бы 
третье — хотя бы четвертое — хотя бы 
Значит, сумма во второй четверке хотя бы
Теперь заметим, что все пары вида
подходят. Действительно (*), если наибольшее число попадает в полуинтервал 
то тогда следующее по размеру не больше, чем 
третье — не больше, чем а четвертое — не больше, чем Аналогично разбирается случай, когда наибольшее число в четверке попадает в интервал 
Значит, любой подходящий вариант может быть сведен к парам такого вида без увеличения суммы. Если
то, очевидно, можно изменить a так, чтобы эти выражения стали равны и ближе друг к другу, максимальное из них, соответственно, уменьшится. Если же
то 
а значит 
Сумма в четверках в этом случае равна
1.1 Найдите a (2, 2).
Пример: наборы и
Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать (1; 0), и набор, в котором оба числа Если это одна и та же пара, то сумма уже Если разные, то посмотрим на набор чтобы набор мажорировал его, должно быть а чтобы набор с парой чисел, больших мажорировал — это должен быть набор, как минимум Легко видеть также, что указанный набор подходит.
Ответ:
1.4 Ограничена ли последовательность 
Сюжет 1
На n карточках написали по k чисел, сумма на каждой карточке равна m. Оказалось, что любой набор из k неотрицательных чисел с суммой 1 можно получить, уменьшив некоторые числа на одной из карточек (наборы неупорядоченные). Пусть a(n, k) — наименьшее m, при котором это возможно.
Вычислим 
Как уже отмечалось, для всякого 
должна быть карточка, в которой 
Если карточка всего одна, то сумма на этой карточке, таким образом, не меньше
С другой стороны, карточка
очевидно, подходит, т. к. в наборе с единичной суммой 
так что
Теперь рассмотрим произвольную пару натуральных чисел 
соотношение
Теперь рассмотрим произвольную пару натуральных чисел соотношение между которыми мы уточним позднее, и предъявим два набора, вдвоём мажорирующих все наборы с единичной суммой: а именно
и
Действительно, рассмотрим любой упорядоченный по убыванию набор 
с единичной суммой. Ясно, что 
при любом i и поэтому первая карточка мажорирует любой набор с единичной суммой, в котором все числа не превосходят 
Пусть, напротив, 
Тогда для любого i имеем
Поэтому любой набор с 
мажорируется второй из наших карточек.
Осталось убедиться, что разность между 
и максимумом из сумм в этих двух наборах может быть сделана (при подходящем выборе l и k) сколь угодно большой. Действительно, сумма на первой карточке отличается от на
и эта величина при достаточно больших l может быть сделана, как известно, сколь угодно большой. Теперь зафиксируем произвольное l и посмотрим на вторую карточку: сумма чисел на ней меньше, чем
на
Поскольку выражение в скобках при фиксированном l и неограниченном k может быть сделано сколь угодно большим, то можно выбрать k так, что эта разность будет больше разности между и первой суммой, которая одним лишь выбором l может быть сделана сколь угодно большой для произвольного 
Утверждение доказано.
Ответ: нет.
1.1 Найдите a (2, 2).
Пример: наборы и
Оценка. Ясно, что должен быть набор, содержащий 1, чтобы мажорировать (1; 0), и набор, в котором оба числа Если это одна и та же пара, то сумма уже Если разные, то посмотрим на набор чтобы набор мажорировал его, должно быть а чтобы набор с парой чисел, больших мажорировал — это должен быть набор, как минимум Легко видеть также, что указанный набор подходит.
Ответ:
Наверх